/**
 * 将数组划分为已排序和未排序两个部分，初始状态下，第一个元素被视为已排序部分。
 * 然后从未排序部分逐个选择元素插入到已排序部分的正确位置，以此逐步构建有序数组。
 * 对于每个待插入元素 current，算法会从已排序部分从后往前遍历，将比 current 大的元素往后移动一个位置，直到找到合适的位置插入 current。
 * https://www.bilibili.com/video/BV1CY4y1t7TZ?p=1&vd_source=3647d6aa8af02fb3eb9258645a51b170
 * 新的元素和已排序的元素从后向前比较，如果小于比较元素，则交换位置，直到已排序的元素中某个位置的值小于当前元素（边界索引为0），则停止比较。
 */
function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      --j;
    }
    arr[j + 1] = current; 
  }
  return arr;
}
const arr = [4, 3, 5, 1, 2];

insertionSort(arr);
console.log(arr, "🍉");

